/*
	Copyright (c) 2009-2011, Stefan Webb.

	This file is part of SimpleML. Please read the file "license.txt", 
	which contains the conditions under which this software is distributed.
*/

/*!
	\file containsnodes.cpp
	\author Stefan Webb
	\brief Definition of ContainsNodes class.
*/

/*! \brief Adds functionality for managing nodes. */
template <class T>
class ContainsNodes
{
public:
	/*! \brief Default constructor. */
	ContainsNodes();

	/*! \brief Constructor with initial memory size.
		\param size Initial number of nodes for which to allocate memory. */
	ContainsNodes(unsigned int size);

	/*! \brief Default destructor. */
	~ContainsNodes();

protected:
	/*! \brief Priority queue containing free nodes. */
	PriorityQueue<> freeNodes_;

	/*! \brief Node bucket. */
	Bucket<T> nodes_;

	/*! \brief Free memory for node and add to free nodes.
		\param node Node to delete. */
	void deleteNode(unsigned int node);

	/*! \brief Get next free node.
		\return Index of next free node. */
	unsigned int nextFreeNode();
};

/* Default constructor. */
template <class T>
ContainsNodes<T>::ContainsNodes()
{
	// By default, allocate 256 nodes.
	ContainsNodes(256);
}

/* Constructor with initial memory size. */
template <class T>
ContainsNodes<T>::ContainsNodes(unsigned int size)
{
	// Allocate initial memory for nodes and free node list
	nodes_.create(size);
	freeNodes_.create(16);	
}

/* Default destructor. */
template <class T>
ContainsNodes<T>::~ContainsNodes()
{
	// Free memory from buckets
	nodes_.destroy();
	freeNodes_.destroy();
}

/* Get next free node */
template <class T>
unsigned int ContainsNodes<T>::nextFreeNode()
{
	// If there is already a free one then return that one
	if (freeNodes_.size())
		return freeNodes_.extract();

	// Otherwise, we will have to make a free node
	else {
		nodes_.addEmpty();
		return nodes_.size() - 1;
	}
}

/* Free memory for node and add to free nodes. */
template <class T>
void ContainsNodes<T>::deleteNode(unsigned int node)
{
	// If it's the last one then remove from bucket
	if (node == nodes_.size() - 1)
		nodes_.pop();

	// Otherwise add to free nodes list
	else
		freeNodes_.insert(node);
}